package com.dataStructure.sort;

import java.util.ArrayList;
import java.util.List;

//实现一个大顶堆，完全二叉树，用数组表示。
//完全二叉树的性质，节点编号0，1，2，3，4.....i
// i节点的父节点编号，i = (i - 1) /2
// 左孩子节点编号为，i = 2 * i + 1。  右孩子节点编号为i = 2 * i + 2;
// 借助ArrayList实现。
//核心两个API，
//poll, add
public class Heap {
    List<Integer> list = new ArrayList<>();

    public Integer poll() {
        int temp = list.get(list.size() - 1);
        list.set(0,temp);
        list.remove(list.size() -1 );

        for (int i = 0; 2 * i + 1 < list.size(); i++) {
            int index = i;
            if (list.get(i) < list.get(2 * i + 1)) {
                index = 2 * i + 1;
            }
            if (2 * i + 2 < list.size() && list.get(index) < list.get(2 * i + 2)) {
                index = 2 * i + 2;
            }

            if (index == i) {
                break;
            }

            //swap
        }

        return temp;
    }
    public void add() {
    }

}









































